package com.hy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最大整除子集
 *
 * 给你一个由无重复正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
 * answer[i] % answer[j] == 0 ，或
 * answer[j] % answer[i] == 0
 * 如果存在多个有效解子集，返回其中任何一个均可。
 *
 *
 * author: Mr.Du
 * Date: 2023/11/20
 * Time: 10:36
 */
public class LargestDivisibleSubset {


    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        // 定义：dp[i] 表示以 nums[i] 这个数结尾的最长符合要求子序列的长度
        List<Integer>[] dp = new List[nums.length];
        for (int i = 0; i < n; i++) {
            dp[i] = new ArrayList<>();
        }
        // base case
        dp[0].add(nums[0]);

        for (int i = 1; i < n; i++) {
            int maxSubsetLen = 0, index = -1;
            // 在 nums[0..i-1] 中寻找那个 nums[i] 能接到结尾的最长子序列
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j].size() > maxSubsetLen) {
                    maxSubsetLen = dp[j].size();
                    index = j;
                }
            }
            // nums[0..i-1] 中最长的那个子序列，再加上 nums[i]，
            // 就是 nums[0..i] 最长的子序列
            if (index != -1) {
                dp[i].addAll(dp[index]);
            }
            dp[i].add(nums[i]);
        }

        List<Integer> res = dp[0];
        for (int i = 1; i < dp.length; i++) {
            if (res.size() < dp[i].size()) {
                res = dp[i];
            }
        }
        return res;
    }


    public List<Integer> largestDivisibleSubset1(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLength = 1, endIndex = 0;  // 记录全局最长子序列的长度和结束位置
        for(int i = 1;i < n;i++){
            for(int j = 0;j < i;j++){
                if(nums[i] % nums[j] == 0){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                if(dp[i] > maxLength){
                    maxLength = dp[i];
                    endIndex = i;
                }
            }
        }
        List<Integer> res = new ArrayList<>();
        res.add(nums[endIndex]);
        maxLength--;
        int tmp = nums[endIndex];
        for (int i = endIndex - 1; i >= 0; i--) {
            if (dp[i] == maxLength && tmp % nums[i] == 0) {
                res.add(nums[i]);
                maxLength--;
                tmp = nums[i];
            }
        }

        Collections.reverse(res);  // 因为是逆序添加的，需要翻转一下得到正确顺序
        return res;

    }

    public static void main(String[] args) {
        LargestDivisibleSubset largestDivisibleSubset = new LargestDivisibleSubset();
        int[] nums = {9,18,54,90,108,180,360,540,720};
        List<Integer> res = largestDivisibleSubset.largestDivisibleSubset1(nums);
        System.out.println(res);

    }
}
